package com.dubious.interview.euler;

import static java.util.Arrays.asList;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

import com.dubious.interview.euler.pandigital.PandigitalNumbers;

public class Problem43 {

    /**
     * The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the
     * digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility
     * property.
     * 
     * Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
     * 
     * d2d3d4=406 is divisible by 2
     * d3d4d5=063 is divisible by 3
     * d4d5d6=635 is divisible by 5
     * d5d6d7=357 is divisible by 7
     * d6d7d8=572 is divisible by 11
     * d7d8d9=728 is divisible by 13
     * d8d9d10=289 is divisible by 17
     * 
     * Find the sum of all 0 to 9 pandigital numbers with this property.
     */
    public static long run()
    {
        // strategy:
        // iterate over 0 to 9 pandigital numbers to find ones that match the criteria
        // note: this is slow. about 20 seconds.
        long sum = 0;
        for(Long number : new PandigitalNumbers(0, 9, 9876543210L))
        {
            if(number < 1000000000)
            {
                // don't check numbers where "first digit is 0"
                break;
            }
            
            // check divisibility of the different parts
            List<Integer> digits = Utilities.extractDigits(number);
            if(!(Utilities.getSubNumber(digits, 1,3) % 2 == 0))
            {
                continue;
            }
            if(!(Utilities.getSubNumber(digits, 2,4) % 3 == 0))
            {
                continue;
            }
            if(!(Utilities.getSubNumber(digits, 3,5) % 5 == 0))
            {
                continue;
            }
            if(!(Utilities.getSubNumber(digits, 4,6) % 7 == 0))
            {
                continue;
            }
            if(!(Utilities.getSubNumber(digits, 5,7) % 11 == 0))
            {
                continue;
            }
            if(!(Utilities.getSubNumber(digits, 6,8) % 13 == 0))
            {
                continue;
            }
            if(!(Utilities.getSubNumber(digits, 7,9) % 17 == 0))
            {
                continue;
            }
            
            sum += number;
        }
        
        return sum;
    }
    
    /**
     * A different implementation.  Faster and slightly more generic.
     * @return
     */
    public static long run2()
    {        
        // strategy: 
        // find 3 digit numbers that are divisible by 17
        // find 3 digit numbers that are divisible by 13 and have last two digits that match one of the 17-divisible digits
        // * 11 * 13-divisible digits
        // etc...
        //
        // then go through all the combinations and check whether they are pandigital
        
        List<Integer> factors = asList(17, 13, 11, 7, 5, 3, 2);
        
        List<Long> specialNumbers = findSpecialNumbers(factors, 0, new LinkedList<Integer>());

        long sum = 0;
        for(Long specialNumber : specialNumbers)
        {
            sum += specialNumber;
        }
        return sum;
    }
    
    public static List<Long> findSpecialNumbers(List<Integer> factors, int factorIndex, List<Integer> setDigits)
    {
        if(factorIndex == factors.size())
        {
            // base case: we have met all the criteria about divisibility
            // all that remains is to find the remaining digit
            Set<Integer> remainingDigits = new HashSet<Integer>(asList(0,1,2,3,4,5,6,7,8,9));
            for(Integer setDigit : setDigits)
            {
                remainingDigits.remove(setDigit);
            }
            
            // there should only be one remainingDigit left
            // note: if the left-over digit is 0 then this number is not special since it is shorter than expected
            Integer remainingDigit = remainingDigits.iterator().next();
            if(remainingDigit != 0)
            {
                List<Integer> newSetDigits = new LinkedList<Integer>(setDigits);
                newSetDigits.add(0, remainingDigit);
                return asList(Utilities.getSubNumber(newSetDigits, 0, newSetDigits.size() - 1));
            }
            
            return Collections.<Long>emptyList();
        }
        
        List<Long> specialNumbers = new ArrayList<Long>();
        // iterate over multiples
        int factor = factors.get(factorIndex);
        int currentFactor = 1;
        while(factor * currentFactor / 1000 == 0)
        {
            int multiple = factor * currentFactor;
            if(multiple >= 10)
            {
                List<Integer> digits = Utilities.extractDigits(multiple);
                if(multiple < 100)
                {
                    // special handling of 2-digit numbers
                    // the 1st digit must be set to 0
                    digits.add(0, 0);
                }
                if(factorIndex == 0)
                {
                    // this is the first factor, the only extra condition is that the multiple have unique digits
                    Set<Integer> uniqueDigits = new TreeSet<Integer>(digits);
                    if(uniqueDigits.size() == 3)
                    {
                        // found a multiple with unique digits
                        specialNumbers.addAll(findSpecialNumbers(factors, factorIndex+1, digits));
                    }
                } else
                {
                    // in the general case the multiple must meet the following criteria:
                    // - last two digits equal first two digits of the "set" digits
                    // - the first digit is unique
                    if(digits.get(1).equals(setDigits.get(0)) && digits.get(2).equals(setDigits.get(1)))
                    {
                        Set<Integer> uniqueDigits = new TreeSet<Integer>(setDigits);
                        uniqueDigits.addAll(digits);
                        if(uniqueDigits.size() == setDigits.size() + 1)
                        {
                            // found a multiple that introduces a new unique digit
                            List<Integer> newSetDigits = new LinkedList<Integer>(setDigits);
                            newSetDigits.add(0, digits.get(0));
                            specialNumbers.addAll(findSpecialNumbers(factors, factorIndex+1, newSetDigits));
                        }
                    }
                }
            }
            
            currentFactor++;
        }
        
        return specialNumbers;
    }
}
